#include <iostream>
#include <unordered_map>

#include "common/utils.hpp"

TreeNode* traversal(std::vector<int>& postorder, std::vector<int>& inorder, int postorderL, int postorderR, int inorderL, int inorderR, std::unordered_map<int, int>& inorderMap) {
    // 没有节点构造二叉树，结束
    if (inorderL >= inorderR || postorderL >= postorderR) return nullptr;

    // 根节点的值
    int nodeValue = postorder[postorderR - 1];
    // 在中序列表中索引
    int inorderIdx = inorderMap[nodeValue];
    TreeNode* node = new TreeNode(nodeValue);
    int lSize = inorderIdx - inorderL;

    node->left = traversal(postorder, inorder, postorderL, postorderL + lSize, inorderL, inorderIdx, inorderMap);
    node->right = traversal(postorder, inorder, postorderL + lSize, postorderR - 1, inorderIdx + 1, inorderR, inorderMap);

    return node;
}

// postorder、inorder中没有重复元素
TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& postorder) {
    // 建立（元素，下标）键值对的哈希表
    std::unordered_map<int, int> inorderValueToIndex;
    for (int i = 0; i < inorder.size(); i++) {
        inorderValueToIndex[inorder[i]] = i;
    }

    return traversal(postorder, inorder, 0, postorder.size(), 0, inorder.size(), inorderValueToIndex);
}

extern TreeNode* commonRoot;

int main() {
    std::vector<int> postorder = { 9,15,7,20,3 };
    std::vector<int> inorder = { 9,3,15,20,7 };
    TreeNode* ret = buildTree(postorder, inorder);
    printTreeNode(ret);
}